Thuật toán tìm đường là gì? Các bài báo nghiên cứu khoa học

Định nghĩa thuật toán tìm đường

Thuật toán tìm đường (pathfinding algorithm) là tập hợp các phương pháp tính toán nhằm xác định một lộ trình hợp lệ hoặc tối ưu từ điểm xuất phát đến điểm đích trong một không gian xác định. Không gian này có thể là mạng lưới các nút trong đồ thị, bản đồ hai chiều trong trò chơi, môi trường ba chiều trong robot học, hoặc thậm chí là các trạng thái trong không gian logic trừu tượng.

Bản chất của thuật toán tìm đường là giải bài toán tối ưu đường đi dưới các ràng buộc nhất định như: khoảng cách ngắn nhất, chi phí thấp nhất, hoặc số bước ít nhất. Các thuật toán khác nhau sẽ áp dụng các chiến lược khác nhau để tìm kiếm đường đi, ví dụ như mở rộng theo chiều rộng (BFS), theo chiều sâu (DFS), theo chi phí tích lũy (Dijkstra), hoặc theo một hàm đánh giá ước lượng (A*).

Thuật toán tìm đường là thành phần cốt lõi trong nhiều hệ thống: định tuyến trong mạng máy tính, chỉ đường GPS, lập kế hoạch chuyển động cho robot, điều hướng nhân vật trong game, và cả trong lĩnh vực logistic, hàng không, trí tuệ nhân tạo. Mỗi lĩnh vực có đặc thù riêng nên yêu cầu lựa chọn thuật toán phù hợp với mục tiêu tối ưu, thời gian xử lý, và độ phức tạp không gian.

Mô hình hóa không gian tìm đường bằng đồ thị

Trước khi áp dụng thuật toán tìm đường, không gian phải được mô hình hóa thành cấu trúc toán học phù hợp, phổ biến nhất là đồ thị. Một đồ thị $G = (V, E)$ gồm:

• $V$: tập hợp các đỉnh (nodes), đại diện cho vị trí, trạng thái, hoặc điểm dữ liệu
• $E$: tập hợp các cạnh (edges), đại diện cho kết nối hoặc đường đi giữa các đỉnh

Mỗi cạnh có thể có trọng số hoặc không. Trong trường hợp có trọng số, mỗi cạnh $(u, v)$ mang giá trị $w(u, v)$ biểu thị chi phí hoặc độ dài của đoạn đường từ $u$ đến $v$.

Ví dụ mô hình bản đồ thành đồ thị:

Đỉnh	Kết nối	Trọng số
A	B, C	5, 2
B	C, D	1, 4
C	D	3

Khi đó, bài toán tìm đường trở thành: tìm chuỗi các đỉnh $[A, C, D]$ sao cho tổng trọng số nhỏ nhất. Việc xây dựng đồ thị chính xác là tiền đề quan trọng cho hiệu quả thuật toán.

Thuật toán tìm đường không có trọng số

Trong một số ứng dụng, chẳng hạn như bản đồ ô vuông trong trò chơi 2D hoặc ma trận logic, chi phí giữa các ô liền kề được xem là bằng nhau. Khi đó, đồ thị trở thành đồ thị không trọng số. Bài toán tìm đường lúc này cần tìm số bước ít nhất giữa hai điểm.

Thuật toán phù hợp trong trường hợp này là Breadth-First Search (BFS). BFS hoạt động bằng cách duyệt từng lớp đỉnh từ nguồn, đảm bảo đỉnh được tìm thấy đầu tiên sẽ là đỉnh gần nhất theo số bước. Do đó, BFS luôn tìm được đường đi ngắn nhất trong đồ thị không trọng số.

• Input: Đồ thị $G = (V, E)$ không có trọng số
• Output: Đường đi có số bước ít nhất từ đỉnh $s$ đến $t$
• Độ phức tạp: $O(|V| + |E|)$

Một số thuật toán khác như DFS (Depth-First Search) có thể tìm đường đi nhưng không đảm bảo ngắn nhất. DFS thường dùng để kiểm tra tính liên thông hoặc tìm tất cả đường có thể, không tối ưu cho bài toán tìm đường ngắn nhất.

Thuật toán tìm đường có trọng số

Trong các hệ thống thực tế, chi phí di chuyển thường khác nhau giữa các đoạn đường, ví dụ như quãng đường xa hơn, tốc độ chậm hơn, hoặc chi phí nhiên liệu cao hơn. Do đó, thuật toán phải xét đến trọng số cạnh khi xác định đường đi tối ưu.

Thuật toán Dijkstra là giải pháp cổ điển cho bài toán tìm đường ngắn nhất trong đồ thị có trọng số không âm. Thuật toán sử dụng một hàng đợi ưu tiên để chọn đỉnh có chi phí nhỏ nhất chưa được xử lý, sau đó cập nhật chi phí đến các đỉnh láng giềng:

$\text{dist}[v] = \min(\text{dist}[v], \text{dist}[u] + w(u, v))$

Với mỗi lần lặp, thuật toán mở rộng vùng ảnh hưởng từ nguồn ra các đỉnh mới cho đến khi đích được tìm thấy hoặc toàn bộ đồ thị được quét. Độ phức tạp trung bình khi dùng heap là $O((|V| + |E|) \log |V|)$.

Dijkstra hoạt động chính xác khi không có cạnh âm. Nếu tồn tại trọng số âm, thuật toán Bellman-Ford được sử dụng thay thế với khả năng phát hiện chu trình âm nhưng có độ phức tạp cao hơn: $O(|V| \cdot |E|)$.

Thuật toán heuristic: A* và các biến thể

A* (A-star) là thuật toán tìm đường có trọng số sử dụng heuristic – một hàm ước lượng chi phí còn lại từ đỉnh hiện tại đến đích – để hướng dẫn việc mở rộng. Đây là sự kết hợp giữa thuật toán Dijkstra (dựa vào chi phí thực tế) và tìm kiếm theo chiến lược thông minh.

Hàm đánh giá của A* là: $f(n) = g(n) + h(n)$, trong đó:

• $g(n)$: chi phí từ điểm bắt đầu đến nút $n$
• $h(n)$: ước lượng chi phí từ $n$ đến đích

Nếu $h(n)$ là admissible (không vượt quá chi phí thực tế), A* đảm bảo tìm được đường đi ngắn nhất.

A* đặc biệt hiệu quả trong bản đồ hai chiều với $h(n)$ là khoảng cách Euclid hoặc Manhattan. Ví dụ: $h(n) = \sqrt{(x_n - x_t)^2 + (y_n - y_t)^2}$ (khoảng cách Euclid), hoặc $h(n) = |x_n - x_t| + |y_n - y_t|$ (Manhattan).

Một số biến thể của A* bao gồm:

• Weighted A*: Nhân hệ số vào heuristic để tăng tốc độ (đánh đổi tính tối ưu)
• IDA* (Iterative Deepening A*): Dùng cho không gian lớn, giới hạn theo $f(n)$
• D* và D*-Lite: Áp dụng trong môi trường động, robot tự điều chỉnh đường đi khi bản đồ thay đổi

So sánh hiệu suất các thuật toán tìm đường

Lựa chọn thuật toán phù hợp phụ thuộc vào loại đồ thị (có trọng số hay không), độ lớn không gian, yêu cầu về tối ưu và thời gian xử lý. Bảng dưới đây tổng hợp một số đặc điểm so sánh:

Thuật toán	Loại đồ thị	Tối ưu	Heuristic	Độ phức tạp
BFS	Không trọng số	Có	Không	$O(|V| + |E|)$
Dijkstra	Trọng số không âm	Có	Không	$O((|V| + |E|)\log |V|)$
Bellman-Ford	Trọng số âm	Có	Không	$O(|V|\cdot|E|)$
A*	Trọng số + heuristic	Có (nếu $h(n)$ đúng)	Có	Phụ thuộc vào không gian và $h(n)$

Heuristic càng gần đúng với chi phí thực tế thì A* càng hiệu quả. Nếu $h(n)$ đánh giá kém, A* có thể mất nhiều tài nguyên như Dijkstra.

Ứng dụng trong thực tiễn

Các thuật toán tìm đường được ứng dụng rộng rãi trong các hệ thống thực tế hiện đại:

• Hệ thống GPS: Dựa trên bản đồ giao thông, A* hoặc Dijkstra xác định đường đi ngắn hoặc nhanh nhất
• Robot tự hành: A*, D*, và RRT giúp robot xác định và thích ứng lộ trình khi môi trường thay đổi
• Game và mô phỏng: NPC trong game sử dụng grid-based A* để tránh vật thể và đến mục tiêu
• Giao thông thông minh: Tối ưu tuyến đường và phân luồng bằng tìm đường dựa trên dữ liệu thời gian thực

Ví dụ: trong trò chơi chiến thuật như StarCraft, mỗi đơn vị sử dụng A* hoặc JPS (Jump Point Search – biến thể tối ưu A*) để di chuyển mượt và tránh va chạm.

Trong hệ thống xe tự lái, thuật toán tìm đường phải được tích hợp với cảm biến, bản đồ HD, và mô-đun kiểm soát chuyển động, đảm bảo vừa chính xác vừa an toàn.

Thuật toán tìm đường trong không gian liên tục

Trong các bài toán hình học tính toán, robot học và vật lý, không gian tìm kiếm có thể là liên tục và nhiều chiều, không thể biểu diễn hoàn toàn bằng đồ thị rời rạc. Các thuật toán lấy mẫu như RRT và PRM ra đời để giải quyết vấn đề này.

• RRT (Rapidly-exploring Random Tree): Xây cây nhị phân mở rộng ngẫu nhiên từ điểm xuất phát đến đích
• PRM (Probabilistic Roadmap): Lấy mẫu các điểm hợp lệ trong không gian, kết nối bằng đường an toàn, sau đó tìm đường trên đồ thị đã xây dựng

Cả hai thuật toán đều hiệu quả với không gian phức tạp, nhiều chướng ngại vật, hoặc có độ tự do cao như tay robot, máy bay, thiết bị bay không người lái. Tuy nhiên, chúng không đảm bảo tối ưu và cần thêm giai đoạn hậu xử lý để làm mượt lộ trình.

RRT* (biến thể của RRT) sử dụng chiến lược tối ưu hóa đường đi dần theo thời gian, hy sinh tốc độ để đổi lấy chất lượng hành trình tốt hơn.

Tài liệu tham khảo

1. Dijkstra, E. W. (1959). "A Note on Two Problems in Connexion with Graphs". Numerische Mathematik.
2. Hart, P. E., Nilsson, N. J., & Raphael, B. (1968). "A Formal Basis for the Heuristic Determination of Minimum Cost Paths". IEEE Transactions on Systems Science and Cybernetics.
3. Russell, S., & Norvig, P. (2021). Artificial Intelligence: A Modern Approach. Pearson.
4. LaValle, S. M. (2006). Planning Algorithms. Cambridge University Press. http://planning.cs.uiuc.edu/
5. MIT OpenCourseWare – Introduction to Algorithms. https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-fall-2011/
6. Stanford CS221: AI Pathfinding Algorithms. https://web.stanford.edu/class/cs221/
7. AAAI – Path Planning Overview. https://www.aaai.org/AITopics/html/path.html